package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/5 15:18
 *
 字符流中第一个不重复的字符：
 1，哈希表+链表：哈希表去重，如果重复且未被删除，删除在链表中的元素
 2，同理哈希表+sb(代替链表，放到FirstAppearingOnce中遍历)
 3，队列+哈希，每次插入都入队，每次检验如果满足（不重复）就返回ch，不满足就弹出（队列空返回#）
 */

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main13 {
    Queue<Character> queue=new LinkedList<>();
    HashMap<Character,Integer>map=new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        queue.add(ch);
        if(map.containsKey(ch)){
            map.put(ch,map.get(ch)+1);
        }else{
            map.put(ch,1);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        while(!queue.isEmpty()){
            char ch=queue.peek();
            if(map.get(ch)==1){
                return ch;
            }else {
                queue.poll();
            }
        }
        return '#';
    }
    /*
    LinkedList<Character>list=new LinkedList<>();
    HashMap<Character,Integer>map=new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(!map.containsKey(ch)){
            map.put(ch,1);
            list.offerLast(ch);
        }else{
            if(map.get(ch)>0){
                for(int i=0;i<list.size();++i){
                    if(list.get(i)==ch){
                        list.remove(i);
                        break;
                    }
                }
                map.put(ch,map.get(ch)-1);
            }
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        if(list.size()==0){
            return '#';
        }else{
            return list.get(0);
        }
    }
    */
}
